package practice;

import dp.Common;

import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

/**
 * 游戏分组
 */
public class GameGroup {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int[] input = Arrays.stream(sc.nextLine().split(" "))
                    .mapToInt(Integer::parseInt)
                    .toArray();
            int sum = Arrays.stream(input).sum();
            int result = solveByRecursive(input, 0,0,0);
            System.out.println(result);
        }
    }

    /**
     * 将一个数组分为2个 使得它们各自总和的差的绝对值最小
     * @param input
     * @param i
     * @param sum1
     * @param sum2
     * @return
     */
    private static int solveByRecursive(int[] input,int i, int sum1,int sum2) {
        if (i == input.length) {
            return Math.abs(sum1-sum2);
        }

        // 将当前元素加入第一个子集
        int r1 = solveByRecursive(input, i + 1, sum1 + input[i], sum2);
        // 将当前元素加入第二个子集
        int r2 = solveByRecursive(input, i + 1, sum1, sum2 + input[i]);
        return Math.min(r1,r2);
    }

    public static int findMinDifference(int[] arr) {
        Arrays.sort(arr);  // 对数组进行排序
        int totalSum = Arrays.stream(arr).sum();  // 计算总和
        int targetSum = totalSum / 2;  // 目标和（因为元素个数为偶数）

        int sum1 = 0;
        int sum2 = 0;
        int halfIndex = 0;

        for (int i = 0; i < arr.length; i++) {
            sum1 += arr[i];
            if (sum1 > targetSum) {
                break;
            }
            halfIndex++;
        }

        sum2 = Arrays.stream(arr, halfIndex, arr.length).sum();  // 计算剩余部分的和

        return Math.abs(sum1 - sum2);
    }

    private static int solveByDp(int[] input,int sum) {
        // dp[i][j] 表示将前 i 个元素分割成两个元素个数为 j 和 i - j 的子数组时，它们总和的差的绝对值的最小值。
        int[][] dp = new int[input.length + 1][sum + 1];

        // 初始化
        for (int j = 0; j <= sum; j++) {
            dp[0][j] = j;
        }

        for (int i = 1; i <= input.length; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j<input[i-1]) {
                    dp[i][j] = Math.min(dp[i][j],dp[i-1][j]);
                } else {
                    dp[i][j] = Math.min(dp[i][j],Math.abs(dp[i-1][j-input[i-1]]) + (sum-j));
                }
            }
        }
        Common.print2dArr(dp);
        return dp[input.length][sum];
    }

    private static int backtrack(int startIndex, int target,int sum,int minSub,List<Integer> inputList,List<Integer> path) {
        if (path.size() == inputList.size()/2) {
            if (Math.abs(sum-target) < minSub) {
                minSub = Math.abs(sum-target);
                return sum;
            }
        }
        for (int i = startIndex; i < inputList.size(); i++) {
            sum+=inputList.get(i);
            path.add(inputList.get(i));
            sum = backtrack(i+1,target,sum,minSub,inputList,path);
            path.remove(path.size()-1);
            sum-=inputList.get(i);
        }
        return sum;
    }

    /**
     * 将一个数组分为2个，使得它们的差的绝对值尽可能小
     * @param arr
     * @return
     */
//    private static int spiltArrAndGetResult(int[] arr) {
//        int[] arr1 = new int[arr.length / 2];
//        int[] arr2 = new int[arr.length / 2];
//        int sum = Arrays.stream(arr).sum();
//
//        for (int i = 0; i < ; i++) {
//
//        }
//    }


}
